package com.sheng.leetcode.year2023.month03.day27;

import org.junit.Test;

/**
 * @author liusheng
 * @date 2023/03/27
 * <p>
 * 1638. 统计只差一个字符的子串数目<p>
 * <p>
 * 给你两个字符串 s 和 t ，请你找出 s 中的非空子串的数目，这些子串满足替换 一个不同字符 以后，是 t 串的子串。<p>
 * 换言之，请你找到 s 和 t 串中 恰好 只有一个字符不同的子字符串对的数目。<p>
 * 比方说， "computer" and "computation" 只有一个字符不同： 'e'/'a' ，所以这一对子字符串会给答案加 1 。<p>
 * 请你返回满足上述条件的不同子字符串对数目。<p>
 * 一个 子字符串 是一个字符串中连续的字符。<p>
 * <p>
 * 示例 1：<p>
 * 输入：s = "aba", t = "baba"<p>
 * 输出：6<p>
 * 解释：以下为只相差 1 个字符的 s 和 t 串的子字符串对：<p>
 * ("aba", "baba")<p>
 * ("aba", "baba")<p>
 * ("aba", "baba")<p>
 * ("aba", "baba")<p>
 * ("aba", "baba")<p>
 * ("aba", "baba")<p>
 * 加粗部分分别表示 s 和 t 串选出来的子字符串。<p>
 * <p>
 * 示例 2：<p>
 * 输入：s = "ab", t = "bb"<p>
 * 输出：3<p>
 * 解释：以下为只相差 1 个字符的 s 和 t 串的子字符串对：<p>
 * ("ab", "bb")<p>
 * ("ab", "bb")<p>
 * ("ab", "bb")<p>
 * 加粗部分分别表示 s 和 t 串选出来的子字符串。<p>
 * <p>
 * 示例 3：<p>
 * 输入：s = "a", t = "a"<p>
 * 输出：0<p>
 * <p>
 * 示例 4：<p>
 * 输入：s = "abe", t = "bbc"<p>
 * 输出：10<p>
 * <p>
 * 提示：<p>
 * 1 <= s.length, t.length <= 100<p>
 * s 和 t 都只包含小写英文字母。<p>
 * <p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/count-substrings-that-differ-by-one-character">1638. 统计只差一个字符的子串数目</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class LeetCode1638 {

    @Test
    public void test01() {
//        String s = "aba", t = "baba";
        String s = "ab", t = "bb";
//        String s = "abe", t = "bbc";
        System.out.println(new Solution().countSubstrings(s, t));
    }
}

class Solution {
    public int countSubstrings(String s, String t) {
        int ans = 0;
        int m = s.length(), n = t.length();
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                // 从 s 和 t 中的不同字符开始
                if (s.charAt(i) != t.charAt(j)) {
                    int l = 0, r = 0;
                    // 向左右延伸直至遇到不同的字符为止
                    while (i - l > 0 && j - l > 0 && s.charAt(i - l - 1) == t.charAt(j - l - 1)) {
                        ++l;
                    }
                    while (i + r + 1 < m && j + r + 1 < n && s.charAt(i + r + 1) == t.charAt(j + r + 1)) {
                        ++r;
                    }
                    // 以该位置为中心，满足条件的子串的对数
                    ans += (l + 1) * (r + 1);
                }
            }
        }
        return ans;
    }
}

//class Solution {
//    public int countSubstrings(String s, String t) {
//        // 满足条件，即，s 中的子串在 t 中也存在，并且子串的左右添加一个字符后不在 t 中存在
//        // 或者是单个字符，并且 t 中有与该字符不同的其他字符时
//        // 或者换一个字符后就能匹配
//        int ans = 0;
//        Set<String> set = new HashSet<>();
//        for (int i = 0; i < t.length(); i++) {
//            set.add(String.valueOf(t.charAt(i)));
//        }
//        for (int i = 0; i < s.length(); i++) {
//            for (int j = i + 1; j <= s.length(); j++) {
//                String substring = s.substring(i, j);
//                if (t.contains(substring)) {
//                    if ((i > 0 && !t.contains(s.substring(i - 1, j))) || (j < s.length() && !t.contains(s.substring(i, j + 1)))) {
//                        ans++;
//                    } else if (set.size() > 1) {
//                        ans++;
//                    }
//                } else if (substring.length() == 1) {
//                    ans++;
//                }
//            }
//        }
//        return ans;
//    }
//}
